In recent years there has been a growing interest in the study of sparse representation of signals. Using an over-complete dictionary that includes prototype signal-atoms, signals are described by sparse linear combinations of these atoms. Applications that use sparse representation are many and include compression, regularization in inverse problems, feature extraction, and so forth. Recent activity in this field has concentrated mainly on the study of pursuit algorithms that decompose signals with respect to a given dictionary. Designing dictionaries to better fit the above model can be done by either selecting one from a pre-specified set of linear transforms or adapting the dictionary to a set of training signals. We are interested in an application that uses sparse representation for video compression.
Introduction of Compressive Sensing (CS) Framework:
Compressive sensing (also referred to as compressive sampling and compressed sensing) is a technique for acquiring and reconstructing a signal in consideration of the prior knowledge that the signal is sparse or compressible.
Supposing x is a length-N signal, x is said to be K-sparse (or compressible) if x can be well approximated using K<<N coefficients under some linear transform Ψ (e.g., the discrete cosine transform (DCT) or the discrete wavelet transform (DWT)) as follows:x=Ψα,  (1)where Ψ is the sparsifying transform, α is the transform coefficient vector, and only K coefficients in α are non-zeroes. Turning to FIG. 1, a representation of a sparse signal is indicated generally by the reference numeral 100. The representation 100 involves a length-N signal x, a sparsifying transform Ψ, and a transform coefficient vector α.
According to the Compressive Sensing (CS) theory applied in a first prior art approach, such a signal can be acquired through the incoherent linear projection as follows:y=Φx,  (2)where y is the measurement vector with M entries, and Φ represents an M×N incoherent sensing matrix. Turning to FIG. 2, a method for measurement acquisition in compressive sensing is indicated generally by the reference numeral 200. The method 200 involves a length-N signal x, a measurement vector with M entries y, and an M×N incoherent sensing matrix Φ.
The CS framework asserts that x can be faithfully recovered from only M˜K log N measurements by solving the following optimization problem:α*=min|α|1 such that y=Φx=ΦΨα*,  (3)and the input signal can be approximated by x*=Ψα*, where α* denotes recovered transform coefficient vector and x* denotes the recovered length-N input signal.Related Work:
In the first prior art approach, a video codec was proposed that encoded a subset of DCT transform coefficients of the block residue and employed a sparse signal recovery algorithm to recover the block residue from the coded coefficients. The sparse signal recovery is obtained through a total-variation (TV) minimization. TV is a function of the difference between consecutive pixels. An example of TV is as follows:TV(x)=Σi|xi−xi-1|.  (4)
Then the problem becomes as follows:min TV(α)s·t·y=Φx=ΦΨα,  (5)where x is the residue data, i.e., the result of subtracting the prediction data from the original data. Basically, the approach tries to minimize the gradient of the reconstructed residue under the constraint of the observed data y. Since a quantization process is involved, perfect reconstruction is not possible in principle (i.e., the equality constraint is too restrictive), so the algorithm allows for some margin of error (denoted by ε in Equation (6)), by solving the following problem:min{μ*TV(x)+∥y−Φx∥2}.  (6)
There are a few critical disadvantages in this approach. For example, the reconstruction algorithm in the first prior art approach employs a TV-minimization based algorithm to reconstruct the block residue. This approach works well assuming the block residue is sparse. However, the block residue is often not sparse in the gradient domain after block prediction, and this assumption is not compatible with the directional intra prediction which has already exploited the spatial redundancy.
To overcome this drawback, we have previously performed research and developed a scheme (hereinafter referred to as the second prior art approach) which proposes to recover the image block directly by applying TV-minimization on the pixel domain. In addition, we propose adjusting the μ adaptively with the quantization parameter so as to compensate quantization noise more efficiently. Although the second prior art approach works well with blocks having a smooth structure and few edges, it is not efficient with textured blocks. This is because textured blocks often are not sparse in the gradient domain.
Finding a domain in which textured blocks have sparse representation is a difficult problem because textured blocks have higher entropy and cannot be de-correlated or compressed efficiently with a fixed transform.
In a third prior art approach, it has been proposed to learn the sparsifying transform, called dictionary, from a training set of images with similar structures. For example, in the third prior art approach, a scheme is proposed in which the idea is to learn the best transform that can sparsify all patches in the training set:min{∥X−ΦS∥}s,t,|Si|0<L  (7)where X is the matrix whose columns are training images or training image patches, Φ is the sparsifying transform or the dictionary to be learned, and S is the matrix of coefficient vectors that are constrained with the number of nonzero entries smaller than some fixed threshold. A method to optimize Equation (7) is called K-SVD. However, there are a few disadvantages in this learning approach. One of the disadvantages is that textured image patches often include different levels of sparsity. Hence, with a fixed sparsity threshold, some of the patches might be over-fitted or under-fitted with this model. This problem becomes more serious when patches are corrupted with quantization noise. This method was developed to tackle de-noising of images, mainly for Gaussian noise.A Typical Video CODEC:
Turning to FIG. 3, a method for encoding image data for a picture is indicated generally by the reference numeral 300. The method 300 includes a start block 310 that passes control to a loop limit block 320. The loop limit block 320 begins a loop using a variable i having a range from 1, . . . , number (#) of blocks in the picture, and passes control to a function block 330. The function block 330 performs intra/inter prediction to obtain a prediction for a current block, and passes control to a function block 340. The function block 340 applies a DCT transform to a residue (representing a difference between an original version of the current block and the prediction for the current block) to obtain transform coefficients there for, and passes control to a function block 350. The function block 350 quantizes the transform coefficients to obtain quantized transform coefficients, and then passes control to a function block 360. The function block 360 entropy codes the quantized transform coefficients, and passes control to a function block 370. The function block 370 inverse quantizes the quantized transform coefficients, and passes control to a function block 380. The function block 380 inverse transforms (using, e.g., an inverse discrete cosine transform (IDCT)) the inverse quantized transform coefficients to obtain a reconstructed residue for the current block, and passes control to a function block 390. The function block 390 reconstructs the current block by adding the reconstructed residue for the current block to the prediction for the current block, and passes control to a loop limit block 395. The loop limit block 395 ends the loop, and passes control to an end block 399.
Turning to FIG. 4, a method for decoding image data for a picture is indicated generally by the reference numeral 400. The method 400 includes a start block 410 that passes control to a loop limit block 420. The loop limit block 420 begins a loop using a variable i having a range from 1, . . . , number (#) of blocks in the picture, and passes control to a function block 430. The function block 430 performs entropy decoding to obtain the quantized transform coefficients, the intra/inter prediction modes and other information, and passes control to a function block 440. The function block 440 inverse quantizes the quantized transform coefficients of the current block, and passes control to a function block 450. The function block 450 inverse transforms (using, e.g., an inverse discrete cosine transform (DCT)) the inverse quantized transform coefficients to obtain a reconstructed residue, and passes control to a function 460. The function block 460 reconstructs the current block by adding the reconstructed residue for the current block to the prediction for the current block, and passes control to a loop limit block 470. The loop limit block 470 ends the loop, and passes control to an end block 499.
Due to quantization, there is quantization noise in a reconstructed block. In accordance with the principles of the present invention, we disclose and describe methods to mitigate the effect of quantization noise.
Our Previous Work:
The aforementioned second prior art approach proposed a video CODEC that incorporated a new compressive sensing coding mode. With this compressive sensing coding mode, instead of encoding all transform coefficients of the block residue, it was proposed to encode only a subset of transform coefficients and disregard the remaining transform coefficients. The transform coefficients were scanned in a zigzag order and the first coefficients were selected as the subset. This subset of transform coefficients was put into a vector that is referred to as a measurement vector of the block residue. The measurement acquisition is mathematically represented as follows:yres=A(xres),  (8)where xres denotes the block residue; yres denotes a vector that includes a subset of the transform coefficients of the block residue; A denotes an operator that transforms the block residue (via the 2-D DCT transform or the integer MPEG-4 AVC Standard transform) and then selects a subset of first entries with respect to the zigzag scanning order.
Given the predicted block and the measurement vector of the block residue yres, the block is reconstructed using the following steps.
Step 1: Generate a measurement vector of the predicted block that contains a subset of significant transform coefficients of block residue, denoted as ypred:ypred=A(xpred)  (9)
Step 2: Generate a measurement vector of the block by adding the measurement vector of block residue to the measurement vector of predicted block:y=yres+ypred  (10)
Step 3: Solve the following optimization for a final reconstructed block:xrec=Arg MinX{Ψ(x)+μ*|y−A(x)|2}  (11)where xrec is a final reconstructed block, Ψ is Total Variation of x, and μ is a weighting factor. The optimization variable is x. Quantization noise is introduced when the measurement vector of block residue yres is quantized. To compensate the quantization noise, the factor μ is adjusted adaptively with respect to the quantization step size.
Turning to FIG. 5, a method for block reconstruction is indicated generally by the reference numeral 500. The method 500 includes a start block 510 that passes control to a function block 520. The function block 520 generates a measurement vector of a predicted block, the measurement vector being a subset of the transform coefficients of the predicted block, and passes control to a function block 530. The function block 530 adds the measurement vector of the predicted block to the (de-quantized) measurement vector of the block residue to yield a measurement vector of a reconstructed block, the measurement vector of the block residue being a subset of the transform coefficients of the block residue and passes control to a function block 540. The function block 540 minimizes the objective function with the measurement vector of the reconstructed block, and passes control to an end block 599.
The new block reconstruction method is incorporated into a video codec as a new compressive sensing coding mode. Based on Rate-Distortion optimization, the encoder decides to encode a block residue using the existing coding modes or the compressive sensing coding mode. For each block with at least a coefficient different from zero, a flag is sent to the decoder to indicate whether or not the encoder employs the compressive sensing mode.
Turning to FIG. 6, a method for encoding image data for a picture is indicated generally by the reference numeral 600. The method 600 advantageously incorporates a novel compressive sensing mode and a novel block reconstruction in accordance with the present principles. The method 600 includes a start block 605 that passes control to a loop limit block 610. The loop limit block 610 begins a loop using a variable i having a range equal to 1, . . . , number (#) of blocks, and passes control to a function block 615. The function block 615 performs intra/inter prediction, and passes control to a function block 620. The function block 620 applies a DCT transform to a residue to obtain the transform coefficients, and passes control to a function block 625. The function block 625 performs coefficient truncation to obtain the measurement vector (by keeping only a subset of the transform coefficients), and passes control to a function block 630. The function block 630 quantizes the (truncated) transform coefficients, and passes control to a function block 635. The function block 635 entropy codes the quantized transform coefficients, and passes control to a function block 640. The function block 640 inverse quantizes the quantized transform coefficients, and passes control to a function block 645. The function block 645 performs block measurement generation, for example using the method 500 in FIG. 5, and passes control to a function block 650. The function block 650 obtains a TV-minimum reconstructed block by solving the optimization problem described in Equation (11), and passes control to a function block 655. The function block 655 performs a rate-distortion computation to obtain a rate-distortion value J1, and passes control to a decision block 690. The decision block 690 determines whether or not J1<J2. If so, then control is passed to a function block 692. Otherwise, control is passed to a function block 694. The function block 692 selects the compressive sensing (CS) coding method, sets CS_flag=1, and passes control to a loop limit block 696. The function block 694 selects the normal coding modes, sets CS_flag=0, and passes control to the loop limit block 696. The loop limit block 696 ends the loop, and passes control to an end block 699. The function block 660 quantizes the transform coefficients, and passes control to a function block 665. The function block 665 entropy codes the quantized transform coefficients, and passes control to a function block 670. The function block 670 inverse quantizes the quantized transform coefficients, and passes control to a function block 675. The function block 675 applies an inverse discrete cosine transform (IDCT) to the quantized transform coefficients to obtain a reconstructed residue, and passes control to a function block 680. The function block 680 adds the reconstructed residue (obtained by function block 680) to the prediction (obtained by function block 615) to obtain a prediction compensated reconstructed block, and passes control to a function block 685. The function block 685 performs a rate-distortion computation to obtain a rate-distortion value J2, and passes control to the decision block 690.
Turning to FIG. 7, a method for decoding image data for a picture is indicated generally by the reference numeral 700. The method 700 advantageously incorporates a novel compressive sensing mode and a novel block reconstruction in accordance with the present principles. The method 700 includes a start block 705 that passes control to a loop limit block 710. The loop limit block 710 begins a loop using a variable i having a range from 1, . . . , number (#) of blocks, and passes control to a function block 715. The function block 715 entropy decodes a bitstream and obtains the quantized transform coefficients of the residue, the Intra/Inter prediction modes, etc., and passes control to a function block 720. The function block 720 reads CS_Flag, and passes control to a decision block 725. The decision block 725 determines whether or not CS_Flag=1. If so, then control is passed to a function block 730. Otherwise, control is passed to a function block 750. The function block 730 inverse quantizes the quantized transform coefficients to obtain the transform coefficients of the residue, and passes control to a function block 735. The function block 735 performs block measurement generation, for example using the method 500 in FIG. 5, and passes control to a function block 740. The function block 740 obtains a TV-minimization reconstructed block by solving the optimization problem in Equation (11), and passes control to a loop limit 745. The loop limit block 745 ends the loop, and passes control to an end block 799. The function block 750 inverse quantizes the quantized transform coefficients of the residue to obtain the transform coefficients, and passes control to a function block 755. The function block 755 applies an inverse transform (e.g., an inverse discrete cosine transform (IDCT)) to the transform coefficients of the residue to reconstruct the residue, and passes control to a function block 760. The function block 760 obtains a prediction compensation reconstructed block by adding the reconstructed residue for the current block to the prediction for the current block, and passes control to the loop limit block 745.
As part of the encoder, our previously proposed method of block reconstruction attempted to reconstruct a block in the image/pixel domain rather than to reconstruct block residue as in the first prior art approach. We employed a 2-D DCT transform (or integer MPEG-4 AVC Standard transform) to obtain transform coefficients of the block residue. To reconstruct the signal, we employed a TV-minimization algorithm to reconstruct the block. Moreover, to compensate for the quantization noise, we adjusted the factor μ in Equation (11) adaptively with respect to the quantization step size.